#ifndef AVLTREE_H
#define AVLTREE_H

#include <iostream>
#include <stdlib.h>
using namespace std;

#define DEBUG_MODE

template<class KEY, class DATA>
class avl_tree 
{
protected:
	class avl_node
	{
	public:
		KEY key;
		DATA data;
		avl_node *Parent, *Right_s, *Left_s;
		int height;
		int BF();
		avl_node(KEY NodeKey, DATA NodeData):key(NodeKey),data(NodeData),Parent(NULL),
						     Right_s(NULL),Left_s(NULL),height(0){}
		~avl_node()
		{
			Parent = NULL;
			Right_s= NULL;
			Left_s= NULL;	
		}
		#ifdef DEBUG_MODE
		void PrintNode()
		{
			int _BF = BF();
	
	
			cout<<"key: "<<key<<" data: "<<data<<" height "<<height<<" BF: "<<_BF<<" ";
			if (Right_s!= NULL)
			{
				cout<<"R_S: "<<Right_s->key;
			}
			if (Left_s!= NULL)
			{
				cout<<" L_S: "<<Left_s->key;
			}
			cout<<endl;
		}
		#endif
		/*end for debug*/
		int NumOfLeaf()
		{
			
			int i = 0;				
			if (Left_s != NULL)
			{
				i+=2;
			}
			if (Right_s != NULL)
			{
				i+=4;
			}				
			return i;
		}
	};
private:
		void updateHeight(avl_node *node);
		void updateHeightForSingle(avl_node* node);
		avl_node* root ;		
		void _InOrderPrint(avl_node* Parent);
		//replace between two nodes in the tree without considering their keys.
		void BlindReplace(avl_node*& Node1,avl_node*& Node2);
		void roll(avl_node* Node);
		avl_node* FindNode(const KEY NodeKey,avl_node* CurrentNode)
		//return a node with the given key
		//in case the key does'nt exist return it's Parent in case the root is NULL return NULL
		{
			if (CurrentNode->key == NodeKey)
			{
				return CurrentNode;
				
			}
			else if (CurrentNode->key < NodeKey)
			{
				if (CurrentNode->Right_s == NULL)
				{
					return CurrentNode;
				}
				else
				{
					return FindNode(NodeKey,CurrentNode->Right_s);
				}
			}
		
			else//(Parent->key > key)
			{
				if (CurrentNode->Left_s == NULL)
				{
					return CurrentNode;
				}
				else
				{
					return FindNode(NodeKey,CurrentNode->Left_s);
				}
				
			}
		}
public:	
		avl_tree()
		{			
			root = NULL;
		}
		virtual ~avl_tree(){}	
		void insert(const KEY key, DATA data);		
		void remove (const KEY key);				
		int& retrive (const KEY key);
		#ifdef DEBUG_MODE
		void InOrderPrint();
		#endif
};

template<class KEY, class DATA>
void avl_tree<KEY, DATA>::roll(avl_node* Node)
{
	int BalanceFactor = Node->BF();
	if (BalanceFactor == 2)
	{
		if (Node->Left_s->BF() >= 0) //((Node->Left_s == NULL) && (Node->Left_s->BF() >= 0))
		{//LL roll
			avl_node *A = Node->Left_s, *B = Node;
			
			if (A->Parent->Left_s == A)
			{
				A->Parent->Left_s = B;
			}
			else if (A->Parent->Right_s == A)
			{
				A->Parent->Right_s = B;
			}
			if (B == root)
			{	
				root = A;
				A->Parent = NULL;
			}
			else
			{
				A->Parent = B->Parent;
			
			}
			B->Parent = A;

			B->Left_s = A->Right_s;
			if (A->Right_s != NULL)
			{
				A->Right_s->Parent = B; 
			}
			A->Right_s = B;
			

			updateHeightForSingle(A);
			updateHeight(B);
		}
		else//p->Left_s->DeltaHeight == -1
		{//LR roll
			avl_node *A = Node->Left_s, *C = Node, *B = Node->Left_s->Right_s;
			if (C->Parent->Left_s == C)
			{
				C->Parent->Left_s = B;
			}
			else if (C->Parent->Right_s == C)
			{
				C->Parent->Right_s = B;
			}
			if (C == root)
			{	
				root = B;
				B->Parent = NULL;
			}
			else
			{
				B->Parent = C->Parent;
			}
			C->Parent = B;
			A->Parent = B;
			
			if (B->Left_s != NULL)
			{
				B->Left_s->Parent = A;
			}
			if (B->Right_s != NULL)
			{
				B->Right_s->Parent = C;
			}

			A->Right_s = B->Left_s;
			C->Left_s = B->Right_s;
			
			B->Left_s = A;
			B->Right_s = C;
			
			updateHeightForSingle(C);
			updateHeightForSingle(A);
			updateHeight(B);
		}
	}
	else//BalanceFactor == -2
	{
		if  (Node->Right_s->BF() <= 0)//((Node->Right_s == NULL) && (Node->Right_s->BF() >= 0))
		{//RR roll
			avl_node *A = Node->Right_s, *B = Node;
			if (A->Parent->Left_s == A)
			{
				A->Parent->Left_s = B;
			}
			else if (A->Parent->Right_s == A)
			{
				A->Parent->Right_s = B;
			}

			if (B == root)
			{	
				root = A;
				A->Parent = NULL;
			}
			else
			{
				A->Parent = B->Parent;
				
			}
			B->Parent = A;

			B->Right_s = A->Left_s;
			if (A->Left_s != NULL)
			{
				A->Left_s->Parent = B; 
			}			
			A->Left_s = B;
			updateHeightForSingle(A);
			updateHeight(B);
			



		}
		else if  (Node->Right_s->BF() == 1)
		{//RL roll
			avl_node *A = Node->Right_s, *C = Node, *B = Node->Right_s->Left_s;
			//dangerus a little tired
			if (C->Parent->Left_s == C)
			{
				C->Parent->Left_s = B;
			}
			else if (C->Parent->Right_s == C)
			{
				C->Parent->Right_s = B;
			}
			if (C == root)
			{	
				root = B;
				B->Parent = NULL;
				
				

			}
			else
			{
				B->Parent = C->Parent;
			}
			C->Parent = B;
			A->Parent = B;
			
			if (B->Left_s != NULL)
			{
				B->Right_s->Parent = A;
			}
			if (B->Right_s != NULL)
			{
				B->Left_s->Parent = C;
			}

			A->Left_s = B->Right_s;
			C->Right_s = B->Left_s;

			B->Right_s = A;
			B->Left_s = C;

			updateHeightForSingle(C);
			updateHeightForSingle(A);
			updateHeight(B);
		}
	}
	
}
template<class KEY, class DATA> 
void avl_tree<KEY,DATA>::updateHeightForSingle(avl_node* node)
{
if (node == NULL)
	{
		return;
	}
	int num = node->NumOfLeaf();
	if (num == 0)
	{
		node->height = 0;	
	}
	else if (num == 2)//has only left sun
	{
		node->height = node->Left_s->height + 1;
	}
	else if(num == 4)  //has right sun
	{
		node->height = node->Right_s->height + 1;
		//node->height = node->Right_s->height + balanceFactor + 1;

	}
	else //num == 6
	{
		if(node->Right_s->height >= node->Left_s->height)
		{
			node->height = node->Right_s->height + 1;
		}
		else
		{
			node->height = node->Left_s->height + 1;
		}
	}

}

template<class KEY, class DATA>
int avl_tree<KEY, DATA>::avl_node::BF() 
{
	int num = NumOfLeaf();
	if (num == 0)
	{
		return 0;
	}
	
	if (num == 2)
	{
		return (1+Left_s->height);
	}
	else if (num == 4)
	{
		return (-1-Right_s->height);
	}
	//else => NumOfLeaf == 6 -the node has two children

	return (Left_s->height - Right_s->height );
}

template<class KEY, class DATA>
void avl_tree<KEY, DATA>::insert(const KEY key, DATA data)// ver2
{
	if (root == NULL)
	{		
		root= new avl_node(key,data);
		return;
	}
		
	avl_node *tempnode = FindNode(key,root);
	if (key == tempnode->key)
	{
		cout<<"error";		
		return;
	}
	
	avl_node* NewNode = new avl_node(key,data);
	NewNode->Parent = tempnode;
	if (key > tempnode->key)
	{
		tempnode->Right_s = NewNode;		
	}
	else //if (key<tempnode->key)
	{
		tempnode->Left_s = NewNode;
		
	}	
	updateHeight(NewNode);
}

template<class KEY, class DATA> 
void avl_tree<KEY,DATA>::updateHeight(avl_node* node)
{
	if (node == NULL)
	{
		return;
	}
	int num = node->NumOfLeaf();
	if (num == 0)
	{
		node->height = 0;	
	}
	else if (num == 2)//has only left sun
	{
		node->height = node->Left_s->height + 1;
	}
	else if(num == 4)  //has right sun
	{
		node->height = node->Right_s->height + 1;
		//node->height = node->Right_s->height + balanceFactor + 1;

	}
	else //num == 6
	{
		if(node->Right_s->height >= node->Left_s->height)
		{
			node->height = node->Right_s->height + 1;
		}
		else
		{
			node->height = node->Left_s->height + 1;
		}
	}
	 int balanceFactor = node->BF();
	if ((balanceFactor == 2) || (balanceFactor == -2))
	{
		roll(node);
	}

	
	updateHeight(node->Parent);
}

template<class KEY, class DATA>
void avl_tree<KEY, DATA>::BlindReplace(avl_node*& Node1,avl_node*& Node2)
{
	avl_node* TempNode;
	if (Node1->key = root->key)
	{
		root = Node2;
	}
	
	TempNode = Node1->Parent;
	Node1->Parent = Node2->Parent;//replace Parent
	Node2->Parent = TempNode;
	
	TempNode = Node1->Right_s;
	Node1->Right_s = Node2->Right_s;
	Node2->Right_s = TempNode;
	
	TempNode = Node1->Left_s;
	Node1->Left_s = Node2->Left_s;
	Node2->Left_s = TempNode;
}

//template<class KEY, class DATA>
//void avl_tree<KEY, DATA>::remove (const KEY key)
//{
//	avl_node *TempNode, *DeletedNodeParent, *Iterator;
//	if (root == NULL)
//	{
//		//tree is empty
//		return;
//	}
//	
//	TempNode = FindNode(key,root); // find the right node
//	if (Iterator->key != key)
//	{
//		//node wasn't found
//	}
//	if ( TempNode->NumOfLeaf() == 0 )
//	{
//		if (TempNode->key < TempNode->Parent->key) //is left sun
//		{
//		TempNode->Parent->Left_s = NULL;
//		}
//		else //  is right sun
//		{
//			TempNode->Parent->Right_s = NULL;
//		}
//		DeletedNodeParent = TempNode->Parent;
//		updateHeight(DeletedNodeParent);
//		delete TempNode;
//		return;
//	}
//
//
//	if ( TempNode->NumOfLeaf() == 2 )
//	{
//		Iterator = TempNode->Right_s;
//		//go to the extrim left--> the smallest
//		while (Iterator->Left_s != NULL)
//		{
//			Iterator = Iterator->Left_s;
//		}
//		BlindReplace(TempNode,Iterator);
//
//	}
//
//	if ( TempNode->NumOfLeaf() == 1 )
//	{
//		//ROSH BAKIR!!
//		
//		if ((TempNode->Parent->key > TempNode->key) && (TempNode->Left_s != NULL))
//		{
//			//Is Left sun and has left Sun 
//			TempNode->Left_s->Parent = TempNode->Parent;//replace the father
//			TempNode->Parent->Left_s= TempNode->Left_s;
//		}
//		else if ((TempNode->Parent->key > TempNode->key) && (TempNode->Right_s != NULL))
//		{
//			//Is Left sun and has Right Sun 
//			TempNode->Right_s->Parent = TempNode->Parent;//replace the father
//			TempNode->Parent->Left_s= TempNode->Right_s;
//		}
//		else if ((TempNode->Parent->key < TempNode->key) && (TempNode->Left_s != NULL))
//		{
//			//Is Right sun and has Left Sun 
//			TempNode->Left_s->Parent = TempNode->Parent;//replace the father
//			TempNode->Parent->Right_s= TempNode->Left_s;
//		}
//		else if ((TempNode->Parent->key < TempNode->key) && (TempNode->Right_s != NULL))
//		{
//			//Is Right sun and has Left Sun 
//			TempNode->Right_s->Parent = TempNode->Parent;//replace the father
//			TempNode->Parent->Right_s= TempNode->Right_s;
//		}
//		
//	}
//}
//

template<class KEY, class DATA>
void avl_tree<KEY, DATA>::remove (const KEY key)
{
	avl_node *TempNode;
	if (root == NULL)
	{
		//tree is empty
		return;
	}
	
	TempNode = FindNode(key,root); // find the right node
	
	if (TempNode->key != key)
	{
		//node wasn't found
	}

	if ( TempNode->NumOfLeaf() == 2 )
	{
		avl_node *Iterator = TempNode->Right_s;
		//go to the extrim left--> the smallest
		while (Iterator->Left_s != NULL)
		{
			Iterator = Iterator->Left_s;
		}
		BlindReplace(TempNode,Iterator);		
	}
	

	if (TempNode == root)
	{
		
		
		if ( TempNode->NumOfLeaf() == 2)//has Left sun
			  {
				  root = TempNode->Left_s;
				  TempNode->Parent = NULL;
			  }
		
		else if (TempNode->NumOfLeaf() == 4)//has Right sun
			  {
				  root = TempNode->Right_s;
				  TempNode->Parent = NULL;
			  }
		else if (TempNode->NumOfLeaf() == 0)//has no sun
			  {
				  root = NULL;
				  delete TempNode;
				  return;
			  }
		
		
	}


	else if ( TempNode->NumOfLeaf() == 1 )
	{
		
		//ROSH BAKIR!!
		
		if ((TempNode->Parent->key > TempNode->key) && (TempNode->Left_s != NULL))
		{
			//Is Left sun and has left Sun 
			TempNode->Left_s->Parent = TempNode->Parent;//replace the father
			TempNode->Parent->Left_s= TempNode->Left_s;
		}
		else if ((TempNode->Parent->key > TempNode->key) && (TempNode->Right_s != NULL))
		{
			//Is Left sun and has Right Sun 
			TempNode->Right_s->Parent = TempNode->Parent;//replace the father
			TempNode->Parent->Left_s= TempNode->Right_s;
		}
		else if ((TempNode->Parent->key < TempNode->key) && (TempNode->Left_s != NULL))
		{
			//Is Right sun and has Left Sun 
			TempNode->Left_s->Parent = TempNode->Parent;//replace the father
			TempNode->Parent->Right_s= TempNode->Left_s;
		}
		else if ((TempNode->Parent->key < TempNode->key) && (TempNode->Right_s != NULL))
		{
			//Is Right sun and has Left Sun 
			TempNode->Right_s->Parent = TempNode->Parent;//replace the father
			TempNode->Parent->Right_s= TempNode->Right_s;
		}
	}
	else if ( TempNode->NumOfLeaf() == 0 )
	{
		if (TempNode->key < TempNode->Parent->key) //is left sun
		{
			TempNode->Parent->Left_s = NULL;
		}
		else //  is right sun
		{
			TempNode->Parent->Right_s = NULL;
		}		
	}	
	{
		avl_node *DeletedNodeParent = TempNode->Parent;
		updateHeight(DeletedNodeParent);
		delete TempNode;
	}
}

template<class KEY, class DATA>
void avl_tree<KEY, DATA>:: InOrderPrint ()
{
	_InOrderPrint(root);	
}

template<class KEY, class DATA>
void avl_tree<KEY, DATA>::_InOrderPrint (avl_node* Node)
{
	if (Node ==NULL){
		return;
	}
	_InOrderPrint(Node->Left_s);
	Node->PrintNode();
	_InOrderPrint(Node->Right_s);
	
}

#endif